#include<stdio.h>
#include<stdlib.h>

typedef struct String {
	char* data;
	int length;
}Str;

void StrAssign(Str&, char*);	
int SubStr(Str, Str);			
void GetNext(Str, int*&);
void GetNextval(Str, int*&);	
int KMP(Str, Str, int*);		
int main(int argc, const char* argv[])
{
	char s[] = "abcabcdabcdeabcdefabcdefg";
	char t[] = "abcdeabcdefab";
	Str S, T;
	int i,idx;
	int* next = NULL, * nextval = NULL;
	
	StrAssign(S, s);
	StrAssign(T, t);
	printf("简单匹配的结果（从1开始）：\n");
	idx = SubStr(S, T);
	if (idx != -1) {
		printf("匹配成功，位置为%d。\n", idx);
	}
	else {
		printf("匹配失败。\n");
	}
	GetNext(T, next);
	printf("next数组：\n");
	for (i = 0; i < T.length; i++) {
		printf("%d\t", next[i]);
	}
	printf("\n");
	GetNextval(T, nextval);
	printf("nextval数组：\n");
	for (i = 0; i < T.length; i++) {
		printf("%d\t", nextval[i]);
	}
	printf("\n");
	printf("使用KMP的结果（从1开始）：\n");
	idx = KMP(S, T, next);
	if (idx != -1) {
		printf("匹配成功，位置为%d。\n", idx);
	}
	else {
		printf("匹配失败。\n");
	}
	printf("使用改进KMP的结果（从1开始）：\n");
	idx = KMP(S, T, nextval);
	if (idx != -1) {
		printf("匹配成功，位置为%d。\n", idx);
	}
	else {
		printf("匹配失败。\n");
	}
	return 0;
}
void StrAssign(Str& S, char* s)	
{
	int i;
	for (i = 0; s[i] != '\0'; i++); 
	S.length = i;	
	S.data = s;		
}
int SubStr(Str S, Str T) 
{
	int i, j;
	for (i = 0; i < S.length; i++) {
		for (j = 0; j < T.length; j++) {
			if (S.data[i + j] != T.data[j])
				break;	
		}
		if (j >= T.length)	
			return (i+1);	
	}
	return -1;
}
void GetNext(Str T, int*& next)
{
	int i, j;
	i = 0;
	j = -1;
	next = (int*)malloc(T.length * sizeof(int));
	while (next == NULL) {	
		next = (int*)malloc(T.length * sizeof(int));
	}
	next[0] = -1;
	while (i < T.length) {
		if (j == -1 || T.data[i] == T.data[j]) {
			i++;
			j++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}
void GetNextval(Str T, int*& nextval)
{
	int i, j;
	i = 0;
	j = -1;
	nextval = (int*)malloc(T.length * sizeof(int));
	while (nextval == NULL) {	
		nextval = (int*)malloc(T.length * sizeof(int));
	}
	nextval[0] = -1;
	while (i < T.length) {
		if (j == -1 || T.data[i] == T.data[j]) {
			i++;
			j++;
			if (T.data[i] != T.data[j])
				nextval[i] = j;
			else
				nextval[i] = nextval[j];
		}
		else
			j = nextval[j];
	}
}
int KMP(Str S, Str T, int* N)
{
	int i, j;
	i = j = 0;
	while (i < S.length && j < T.length) {
		if (j == -1 || S.data[i] == T.data[j]) {
			i++;
			j++;
		}
		else
			j = N[j];	
	}
	if (j >= T.length)
		return (i+1-T.length);	
	else
		return -1;
}
